<!doctype html>
<html>
	<head>
		<title>quadtree-js Simple Demo</title>
		<link rel="stylesheet" type="text/css" href="style.css?v=2" />
		<meta name="viewport" content="width=device-width, initial-scale=1" />

		<!-- prism syntax highlighting (https://prismjs.com/) -->
		<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/prism/1.21.0/themes/prism.min.css" integrity="sha512-tN7Ec6zAFaVSG3TpNAKtk4DOHNpSwKHxxrsiw4GHKESGPs5njn/0sMCUMl2svV4wo4BK/rCP7juYz+zx+l6oeQ==" crossorigin="anonymous" />
	</head>
	<body>

		<div class="outer">
			
			<h1><a href="https://github.com/timohausmann/quadtree-js">quadtree-js</a> <small>simple example</small></h1>

			<nav class="nav">
				<strong>Demos:</strong>
				<span>simple</span>
				<a href="dynamic.html">dynamic</a>
				<a href="many.html">many to many</a>
				<a href="test-retrieve.html">benchmark</a>
			</nav>
			
			<div id="canvasContainer">
				<canvas id="canvas" width="640" height="480"></canvas>
			</div>

			<div class="ctrl">
				<div class="ctrl-left">
					<button id="btn_add">add small object</button>
					<button id="btn_add_big">add big object</button>
					<button id="btn_add_10">add 10 small objects</button>
					<button id="btn_clear">clear tree</button>
				</div>

				<div class="ctrl-right">
					Total Objects: <span id="cnt_total">0</span><br />
					Candidates: <span id="cnt_cand">0</span> (<span id="cnt_perc">0</span>%)
				</div>
			</div>

			<p>
				This quadtree starts off empty. Click the buttons to add elements to the Quadtree.
			</p>
			<p>
				After adding five objects to the Quadtree it will split, because we initially set <code>max_objects</code> to 4.
			</p>
			<pre><code class="language-javascript">var myTree = new Quadtree({
	x: 0,
	y: 0,
	width: 640,
	height: 480
}, 4);</code></pre>

			<p>
				Objects that you insert into the tree need to have <code>x</code>, <code>y</code>, <code>width</code> and <code>height</code> properties in order to work.
				Of course you can extend these objects with your own data.
			</p>
			<pre><code class="language-javascript">var myObject = {
	x: 200,
	y: 100,
	width: 35,
	height: 70
}

myTree.insert(myObject);</code></pre>

			
			<p>
				In this example, we constantly retrieve collision candidates for the white area at your mouse cursor. The candidates are highlighted in green.
			</p>

			<pre><code class="language-javascript">var myCursor = {
	x: mouseX,
	y: mouseY,
	width: 20,
	height: 20
};

var candidates = myTree.retrieve(myCursor);</code></pre>
			<p>
				The object passed to the retrieve function does not have to be inside the quadtree. It could be though, if that's your thing. 
			</p>
			
			<p>
				What you get is an array of your collision candidates. In this example, we will only mark them with a <code>check</code>-property to paint them green. In a real world example, you may want to check them for collisions.
			</p>

			<pre><code class="language-javascript">for(var i=0;i&lt;candidates.length;i=i+1) {
	candidates[i].check = true;
}</code></pre>
				

			<p>
				Run clear() to remove all objects from the quadtree and reset it.
			</p>

			<pre><code class="language-javascript">myTree.clear();</code></pre>

			<p>
				To see the full example code please check the page source or 
				<a href="https://github.com/timohausmann/quadtree-js/tree/master/docs" target="_blank" rel="noopener noreferrer">visit GitHub</a>.
			</p>
			
		</div>

		<!-- github corner (https://github.com/tholman/github-corners) -->
		<a href="https://github.com/timohausmann/quadtree-js" class="github-corner" aria-label="View source on GitHub"
			target="_blank" rel="noopener noreferrer">
			<svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true">
				<path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path>
			</svg>
		</a>

		<!-- prism syntax highlighting -->
		<script src="https://cdnjs.cloudflare.com/ajax/libs/prism/1.21.0/prism.min.js" integrity="sha512-WkVkkoB31AoI9DAk6SEEEyacH9etQXKUov4JRRuM1Y681VsTq7jYgrRw06cbP6Io7kPsKx+tLFpH/HXZSZ2YEQ==" crossorigin="anonymous"></script>

		<!-- quadtree lib and script -->
		<script src="./quadtree.min.js"></script>
		<!-- CDN alternative: -->
		<!-- <script src="https://cdn.jsdelivr.net/npm/@timohausmann/quadtree-js/quadtree.min.js"></script> -->
		<script>
		
		(function(w, M) {
			
			w.requestAnimFrame = (function () {
				return  w.requestAnimationFrame ||
					w.webkitRequestAnimationFrame ||
					w.mozRequestAnimationFrame ||
					w.oRequestAnimationFrame ||
					w.msRequestAnimationFrame ||
					function (callback) {
						w.setTimeout(callback, 1000 / 60);
					};
			})();
			
			/*
			 * the main Quadtree
			 */
			var myTree = new Quadtree({
				x: 0,
				y: 0,
				width: 640,
				height: 480
			}, 4);
			
			/*
			 * our objects will be stored here
			 */
			var myObjects = [];


			/*
			 * our "hero", aka the mouse cursor.
			 * He is not in the quadtree, we only use this object to retrieve objects from a certain area
			 */
			var myCursor = {
				x : 0,
				y : 0,
				width : 28,
				height : 28
			};

			var isMouseover = false;
			
			var ctx = document.getElementById('canvas').getContext('2d');

			var cnt_total = document.querySelector('#cnt_total'),
				cnt_cand = document.querySelector('#cnt_cand'),
				cnt_perc = document.querySelector('#cnt_perc');
			

			/*
			 * position hero at mouse
			 */
			var handleMousemove = function(e) {
				
				isMouseover = true;
				
				if(!e.offsetX) {
					e.offsetX = e.layerX - e.target.offsetLeft;
					e.offsetY = e.layerY - e.target.offsetTop;
				} 
				
				myCursor.x = e.offsetX - (myCursor.width/2);
				myCursor.y = e.offsetY - (myCursor.height/2);		
			};


			/*
			 * hide hero
			 */
			var handleMouseout = function(e) {
				
				isMouseover = false;
			};


			
			/*
			 * add a random object to our simulation
			 */
			var handleAdd = function(rect) {

				if(!rect) {
					rect = {
						x : randMinMax(0, myTree.bounds.width-32),
						y : randMinMax(0, myTree.bounds.height-32),
						width : randMinMax(4, 32, true),
						height : randMinMax(4, 32, true),
						check : false
					};
				}

				//store object in our array
				myObjects.push(rect);

				//insert object in our quadtree
				myTree.insert(rect);

				//update total counter
				updateTotal();
			}
			
			/*
			 * clear the tree
			 */
			var handleClear = function() {

				//empty our array
				myObjects = [];

				//empty our quadtree
				myTree.clear();

				//update total counter
				updateTotal();				
			}
			
			
			/*
			 * draw Quadtree nodes
			 */
			var drawQuadtree = function(node) {

				var bounds = node.bounds;
			
				//no subnodes? draw the current node
				if(node.nodes.length === 0) {
					ctx.strokeStyle = 'rgba(255,0,0,0.5)';
					ctx.strokeRect(bounds.x, bounds.y, bounds.width, bounds.height);
					
				//has subnodes? drawQuadtree them!
				} else {
					for(var i=0;i<node.nodes.length;i=i+1) {
						drawQuadtree(node.nodes[i]);
					}
				}
			};
			
			/*
			 * draw all objects
			 */
			var drawObjects = function() {
				
				var obj;
				
				for(var i=0;i<myObjects.length;i=i+1) {
					
					obj = myObjects[i];
					
					if(obj.check) {
						ctx.fillStyle = 'rgba(48,255,48,0.5)';
						ctx.fillRect(obj.x, obj.y, obj.width, obj.height);
					} else {
						ctx.strokeStyle = 'rgba(255,255,255,0.5)';
						ctx.strokeRect(obj.x, obj.y, obj.width, obj.height);
					}
					
					
				}
			};

			
			/**
			 * return a random number within given boundaries.
			 *
			 * @param {number} min		the lowest possible number
			 * @param {number} max		the highest possible number
			 * @param {boolean} round	if true, return integer
			 * @return {number} 		a random number
			 */
			randMinMax = function(min, max, round) {
				var val = min + (Math.random() * (max - min));
				
				if(round) val = Math.round(val);
				
				return val;
			};
			
			/*
			 * our main loop
			 */
			var loop = function() {
				
				var candidates = [];
				
				ctx.clearRect(0, 0, 640, 480);
				
				//reset myObjects check flag
				for(var i=0;i<myObjects.length;i=i+1) {
					
					myObjects[i].check = false;
				}
				

				if(isMouseover) {

					ctx.fillStyle = 'rgba(255,255,255,0.5)';
					ctx.fillRect(myCursor.x, myCursor.y, myCursor.width, myCursor.height);
					
					//retrieve all objects in the bounds of the hero 
					candidates = myTree.retrieve(myCursor);

					//flag retrieved objects
					for(i=0;i<candidates.length;i=i+1) {
						candidates[i].check = true;
					}
				}

				updateCandidatesInfo(candidates);
				
				drawQuadtree(myTree);

				drawObjects();
				
				requestAnimFrame(loop);
			};


			var updateTotal = function() {

				cnt_total.innerHTML = myObjects.length;
			}

			var updateCandidatesInfo = function(candidates) {

				cnt_cand.innerHTML = candidates.length;
				if(!myObjects.length) return;
				cnt_perc.innerHTML = Math.round((candidates.length/myObjects.length)*100);
			}
						
			//init first loop
			loop();
			
			//set eventListener for mousemove
			document.getElementById('canvas').addEventListener('mousemove', handleMousemove);
			document.getElementById('canvas').addEventListener('mouseout', handleMouseout);

			//set eventListener for buttons
			document.getElementById('btn_add').addEventListener('click', function() {
				handleAdd();
			});
			document.getElementById('btn_add_big').addEventListener('click', function() {
				handleAdd({
					x : randMinMax(0, myTree.bounds.width/2),
					y : randMinMax(0, myTree.bounds.height/2),
					width : randMinMax(myTree.bounds.height/4, myTree.bounds.height/2, true),
					height : randMinMax(myTree.bounds.height/4, myTree.bounds.height/2, true),
					check : false
				});
			});
			document.getElementById('btn_add_10').addEventListener('click', function() {
				for(var i=0;i<10;i++) { handleAdd() };
			});
			document.getElementById('btn_clear').addEventListener('click', handleClear);

			
		})(window, Math);
		</script>
	</body>
</html>
